import java.util.*;

public class Solution {
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    //只出现一次的数字
    public int singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if(set.contains(nums[i])){//如果set里面已经包含这个元素
                set.remove(nums[i]);
            }else {
                set.add(nums[i]);
            }
        }
        
        //在遍历一遍里面就是只有一个的数字
        for (int i = 0; i <nums.length ; i++) {
            if(set.contains(nums[i])){//如果set里面已经包含这个元素
                return nums[i];
            }
        }
        return 0;
    }

    //克隆随机链表
    public Node copyRandomList(Node head) {
        HashMap<Node,Node> map = new HashMap<>();
        Node cur = head;
        while(cur != null){
            //cur 老节点 node 新节点 val是值，不变 cur和node一一对应
            Node node = new Node(cur.val);
            map.put(cur,node);
            cur = cur.next;
        }

        cur = head;
        while(cur != null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
        }
        return map.get(head);
    }


    //宝石与石头
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        for (char ch: jewels.toCharArray()) {
            set.add(ch);
        }

        int count = 0 ;
        for (char ch: stones.toCharArray()) {
            if(set.contains(ch)){
                count++;
            }
        }
        return count;
    }




    //坏键盘打字
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String s1 = in.nextLine();
            String s2 = in.nextLine();
            func(s1,s2);
        }


    }
    //func方法用于实现把坏的字符分离出,s1代表输入的全部字符，s2代表实际输出的字符
    private static void func(String s1, String s2) {
        Set<Character> set1 = new HashSet<>();
        //把s2中的元素转换成大写再转换成数组并加入set1
        for (char ch: s2.toUpperCase().toCharArray()) {
            set1.add(ch);
        }

        Set<Character> set2 = new HashSet<>();
        for (char ch: s1.toUpperCase().toCharArray()) {
            if(!set1.contains(ch)){
                System.out.print(ch);
               set2.add(ch);
            }
        }

    }




    //统计单词出现的次数(普通）
    public static void main(String[] args) {
        String[] words = {"this","man","this","woman","happy","day","happy"};
        WordCount(words);
        func(words);
    }

    public static void WordCount(String[] words){
        //排序，方便后面比较
        Arrays.sort(words);

        //存放 不同的单词和单词出现的次数
        String[] uniqueWords = new String[words.length];
        int[] wordCounts = new int[words.length];
        int uniqueWordCount = 0;

        for (String word : words) {
            if(uniqueWordCount == 0 || !word.equals(uniqueWords[uniqueWordCount -1])){//第一次添加或者两个相邻的单词不同
                uniqueWords[uniqueWordCount] = word;
               wordCounts[uniqueWordCount]=1;
               uniqueWordCount++;
            }else {
                //上一个不同单词的计数加 1
                wordCounts[uniqueWordCount-1]++;
            }
        }
        for (int i = 0; i < uniqueWordCount; i++) {
            System.out.println(uniqueWords[i] + " 出现的次数: " + wordCounts[i]);
        }
    }



    /*
    * 统计单词出现的次数(HashMap)
    * */

    public static void func(String[] words) {
        Map<String,Integer> map = new HashMap<>();
        for (String word :words) {
            if(map.get(word)==null){//说明map里面没有这个单词
                map.put(word,1);
            }else {//已经存在
                int val = map.get(word);
                map.put(word,val+1);
            }
        }

        System.out.println(map);
    }

    //前k个高频词汇
    public List<String> topKFrequent(String[] words, int k) {

        //统计每个单词出现的次数
        Map<String,Integer> map = new HashMap<>();
        for (String word :words) {
            if(map.get(word)==null){//说明map里面没有这个单词
                map.put(word,1);
            }else {//已经存在
                int val = map.get(word);
                map.put(word,val+1);
            }
        }
        //2、建立小根堆,指定比较的方式
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>
                (new Comparator<Map.Entry<String, Integer>>() {
                    @Override
                    public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {

                        //如果频率相同
                        if(o1.getValue().compareTo(o2.getValue()) == 0) {
                            //按照字母顺序建立大根堆
                            return o2.getKey().compareTo(o1.getKey());
                        }

                        return o1.getValue()-o2.getValue();
                    }
                });

        //3、遍历map 调整优先级队列

        for(Map.Entry<String,Integer> entry: map.entrySet()) {
            if(minHeap.size() < k) {
                minHeap.offer(entry);
            }else {
                Map.Entry<String,Integer> top = minHeap.peek();
                //如果当前频率相同
                if(top.getValue().compareTo(entry.getValue()) == 0) {
                    // 字母顺序小的进来
                    if(top.getKey().compareTo(entry.getKey()) > 0) {
                        //出队
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }else {
                    if(top.getValue().compareTo(entry.getValue()) < 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }

        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> top  = minHeap.poll();
            ret.add(top.getKey());
        }

        //逆置
        Collections.reverse(ret);

        return ret;



    }


}
